Coin path

Time: O(NxB); Space: O(N); hard

Given an array A (index starts at 1) consisting of N integers: A1, A2, …, AN and an integer B. The integer B denotes that from any place (suppose the index is i) in the array A, you can jump to any one of the place in the array A indexed i+1, i+2, …, i+B if this place can be jumped to. Also, if you step on the index i, you have to pay Ai coins. If Ai is -1, it means you can’t jump to the place indexed i in the array.

Now, you start from the place indexed 1 in the array A, and your aim is to reach the place indexed N using the minimum coins. You need to return the path of indexes (starting from 1 to N) in the array you should take to get to the place indexed N using minimum coins.

If there are multiple paths with the same cost, return the lexicographically smallest such path.

If it’s not possible to reach the place indexed N then you need to return an empty array.

Notes:

  • Path Pa1, Pa2, …, Pan is lexicographically smaller than Pb1, Pb2, …, Pbm, if and only if at the first i where Pai and Pbi differ, Pai < Pbi; when no such i exists, then n < m.

  • A[0] >= 0. A[1], …, A[N-1] (if exist) will in the range of [-1, 100].

  • Length of A is in the range of [1, 1000].

  • B is in the range of [1, 100].

Example 1:

Input：A = [1,2,3,4,5]，B=2

Output：[1,3,5]

Explanation:

  • 9 is the smallest cost

Example 2:

Input：A = [1,2,4,-1,2]，B=1

Output：[]

Explanation

  • There is no path from 1 to n

[1]:

class Solution1(object):
    """
    Time: O(N*B)
    Space: O(N)
    """
    def cheapestJump(self, A, B):
        """
        :type A: List[int]
        :type B: int
        :rtype: List[int]
        """
        result = []
        if not A or A[-1] == -1:
            return result

        n = len(A)
        dp, next_pos = [float("inf")] * n, [-1] * n
        dp[n-1] = A[n-1]

        for i in reversed(range(n-1)):
            if A[i] == -1:
                continue
            for j in range(i+1, min(i+B+1,n)):
                if A[i] + dp[j] < dp[i]:
                    dp[i] = A[i] + dp[j]
                    next_pos[i] = j
        if dp[0] == float("inf"):
            return result
        k = 0

        while k != -1:
            result.append(k+1)
            k = next_pos[k]

        return result

[2]:

s = Solution1()

A = [1,2,3,4,5]
B=2
assert s.cheapestJump(A, B) == [1,3,5]

A = [1,2,4,-1,2]
B=1
assert s.cheapestJump(A, B) == []